package codetop;

import java.util.*;
import java.util.Map;

public class LRU2 {
    public static void main(String[] args) {

    }
    static class Node {
        int key, value;
        Node left, right;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class doubleList {
        int size;
        Node head ;
        Node tail;
        public doubleList() {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.right = tail;
            tail.left = head;
            size = 0;
        }
        public void addNode(Node node){
            node.right = tail;
            node.left = tail.left;
            tail.left.right = node;
            tail.left = node;
            size++;
        }
        public void removeNode(Node node){
            node.left.right = node.right;
            node.right.left = node.left;
            size--;
        }
        public Node removeFirst(){
            if(size == 0)
                return null;
            Node re = head.right;
            removeNode(re);
            return re;
        }
        public int length_node(){
            return size;
        }

    }

    static class LRUCache {
        int capacity;
        Map<Integer, Node> map = new HashMap<>();
        doubleList cache = new doubleList();
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }
        public void makeRecently(int key){
            Node x = map.get(key);
            cache.removeNode(x);
            cache.addNode(x);
        }
        public void addRecently(int key, int val){
            Node node = new Node(key, val);
            cache.addNode(node);
            map.put(key,node);
        }
        public void deleteKey(int key){
            Node node = map.get(key);
            cache.removeNode(node);
            map.remove(key);
        }

        private void removeLeastRecently() {
            Node deletedNode = cache.removeFirst();
            int deletedKey = deletedNode.key;
            map.remove(deletedKey);
        }
        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            makeRecently(key);
            return map.get(key).value;
        }

        public void put(int key, int value) {
            if(map.containsKey(key)){
                deleteKey(key);
                addRecently(key, value);
                return;
            }
            if(capacity == cache.size){
                removeLeastRecently();
            }
            addRecently(key, value);
        }
    }
}
